package com.example.sword;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Test24 {

    public static void main(String[] args) {

    }


    public class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;

        TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
     */

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (root==null)return ans;
        int sum = 0;
        ArrayList<Integer> list = new ArrayList<>();
        search(root,sum,target,ans,list);
        return ans;
    }

    public void search(TreeNode root,int sum, int target,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list){


        if (sum==target&&root==null&&!ans.contains(list)) {
            ans.add(list);
            return;
        }
        if (root==null)return;

        sum+=root.val;
        //路径上的每个值都添加进去
        list.add(root.val);
        if (sum>target)return;

        search(root.left,sum,target,ans,new ArrayList<>(list));
        search(root.right,sum,target,ans,new ArrayList<>(list));

    }

}
